﻿#include "Heap.h"

void HeapInit(Heap* php)
{
	assert(php);
	php->_a = NULL;
	php->_capacity = php->_size = 0;

}

void HeapDestory(Heap* hp)
{
	assert(hp);
	if (hp->_a)
	{
		free(hp->_a);
	}
	hp->_capacity = hp->_size = 0;

}

void Hpwap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}


void Adjustup(HPDataType *a, int son)
{
	
	int father = ( son - 1) / 2;
	while (son > 0)
	{
		if (a[son] > a[father])
		{
			Hpwap(&a[son], &a[father]);
			son = father;
			father = (son - 1) / 2;
		}
		else
		{
			break;
		}
	}
	

}

void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->_capacity == hp->_size)
	{
		int newcapacity = hp->_capacity == 0 ? 4 : 2 * hp->_capacity;
		HPDataType* tmp = realloc(hp->_a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("HeapPush::realloc");
			exit(1);
		}
		hp->_a = tmp;
		hp->_capacity = newcapacity;
	}
	hp->_a[hp->_size] = x;

	Adjustup(hp->_a, hp->_size);
	hp->_size++;

}


void Adjustdown(HPDataType* a, int father , int n)
{

	int son = 2*father + 1;
	while (son < n)
	{
		if (son + 1 < n && a[son] < a[son + 1])
		{
			son = son + 1;
		}

		if (a[father] < a[son])
		{
			Hpwap(&a[father], &a[son]);

		}
		else
		{
			break;
		}
		father = son;
		son = 2 * father + 1;
	}

}

void HeapPop(Heap* hp)
{
	assert(hp&&hp->_size);
	Hpwap(&hp->_a[0], &hp->_a[hp->_size-1]);
	hp->_size--;
	Adjustdown(hp->_a,0,hp->_size);
}

bool HeapEmpty(Heap* hp)
{
	assert(hp);

	return hp->_size == 0;

}

int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->_size;
}

HPDataType HeapTop(Heap* hp)

{
	assert(hp);

	if (!HeapEmpty(hp))
	{
		return hp->_a[0];
	}
	else
	{
		return -1;
	}

}
